{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Tic-Tac-Toe LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #counting #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #计数 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tictactoe"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #井字游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>设计一个算法，判断玩家是否赢了井字游戏。输入是一个 N x N 的数组棋盘，由字符&quot; &quot;，&quot;X&quot;和&quot;O&quot;组成，其中字符&quot; &quot;代表一个空位。</p>\n",
    "\n",
    "<p>以下是井字游戏的规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>玩家轮流将字符放入空位（&quot; &quot;）中。</li>\n",
    "\t<li>第一个玩家总是放字符&quot;O&quot;，且第二个玩家总是放字符&quot;X&quot;。</li>\n",
    "\t<li>&quot;X&quot;和&quot;O&quot;只允许放置在空位中，不允许对已放有字符的位置进行填充。</li>\n",
    "\t<li>当有N个相同（且非空）的字符填充任何行、列或对角线时，游戏结束，对应该字符的玩家获胜。</li>\n",
    "\t<li>当所有位置非空时，也算为游戏结束。</li>\n",
    "\t<li>如果游戏结束，玩家不允许再放置字符。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果游戏存在获胜者，就返回该游戏的获胜者使用的字符（&quot;X&quot;或&quot;O&quot;）；如果游戏以平局结束，则返回 &quot;Draw&quot;；如果仍会有行动（游戏未结束），则返回 &quot;Pending&quot;。</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> board = [&quot;O X&quot;,&quot; XO&quot;,&quot;X O&quot;]\n",
    "<strong>输出：</strong> &quot;X&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> board = [&quot;OOX&quot;,&quot;XXO&quot;,&quot;OXO&quot;]\n",
    "<strong>输出：</strong> &quot;Draw&quot;\n",
    "<strong>解释：</strong> 没有玩家获胜且不存在空位\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> board = [&quot;OOX&quot;,&quot;XXO&quot;,&quot;OX &quot;]\n",
    "<strong>输出：</strong> &quot;Pending&quot;\n",
    "<strong>解释：</strong> 没有玩家获胜且仍存在空位\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= board.length == board[i].length &lt;= 100</code></li>\n",
    "\t<li>输入一定遵循井字棋规则</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [tic-tac-toe-lcci](https://leetcode.cn/problems/tic-tac-toe-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [tic-tac-toe-lcci](https://leetcode.cn/problems/tic-tac-toe-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"OX \",\"OX \",\"O  \"]', '[\"O\"]', '[\"OOXXOXXX\",\"XXXOXOXO\",\"OXOXXXOO\",\"XOXOXXXX\",\"OXOOXOOO\",\"XOOOOOOO\",\"OXXXOOOX\",\"XOXOOXXX\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            s = c * n\n",
    "            return any((\n",
    "                any(row == s for row in board),\n",
    "                any(col == s for col in map(''.join, zip(*board))),\n",
    "                all(board[i][i] == c for i in range(n)),\n",
    "                all(board[i][n - i - 1] == c for i in range(n))\n",
    "            ))\n",
    "        if check('X'):\n",
    "            return 'X'\n",
    "        if check('O'):\n",
    "            return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n=len(board)\n",
    "        def check(c):\n",
    "            s=c*n\n",
    "            return any(raw==s for raw in board) or any(col==s for col in map(\"\".join,zip(*board))) or all(board[i][i]==c for i in range(n)) or all(board[i][n-1-i]==c for i in range(n))\n",
    "        \n",
    "        if check(\"X\"):\n",
    "            return \"X\"\n",
    "        if check(\"O\"):\n",
    "            return \"O\"\n",
    "        if \" \" in \"\".join(board):\n",
    "            return \"Pending\"\n",
    "        return \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        diag,diag1 = '',''\n",
    "        column = ['']*n\n",
    "        over = True\n",
    "        for i in range(n):\n",
    "            if ' 'in board[i]:\n",
    "                over = False\n",
    "            for j in range(n):\n",
    "                if i==j:\n",
    "                    diag+=board[i][j]\n",
    "                if i+j==n-1:\n",
    "                    diag1+=board[i][j]\n",
    "                column[j]+=board[i][j]\n",
    "        board += column+[diag,diag1]\n",
    "        for c in board:\n",
    "            if len(set(c))==1 and ' ' not in c:\n",
    "                return c[0]\n",
    "        return 'Draw' if over else 'Pending'\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(t):\n",
    "            for x in board:\n",
    "                s = set(x)\n",
    "                if t in s and len(s) == 1:\n",
    "                    return True\n",
    "            for x in zip(*board):\n",
    "                s = set(x)\n",
    "                if t in s and len(s) == 1:\n",
    "                    return True\n",
    "            s0 = set()\n",
    "            s1 = set()\n",
    "            for i in range(n):\n",
    "                s0.add(board[i][i])\n",
    "                s1.add(board[i][n-1-i])\n",
    "            if (t in s0 and len(s0) == 1) or (t in s1 and len(s1) == 1):\n",
    "                return True\n",
    "            return False\n",
    "        if check('X'): return 'X'\n",
    "        if check('O'): return 'O'\n",
    "        for i, row in enumerate(board):\n",
    "            for j, x in enumerate(row):\n",
    "                if x == ' ':\n",
    "                    return 'Pending'\n",
    "        return 'Draw'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        black = False\n",
    "        for i in range(n):\n",
    "            row_o_cnt = 0\n",
    "            col_o_cnt = 0\n",
    "            row_x_cnt = 0\n",
    "            col_x_cnt = 0\n",
    "            for j in range(n):\n",
    "                if board[i][j] == 'O':\n",
    "                    row_o_cnt += 1\n",
    "                elif board[i][j] == 'X':\n",
    "                    row_x_cnt += 1\n",
    "                else:\n",
    "                    black = True\n",
    "                if board[j][i] == 'O':\n",
    "                    col_o_cnt += 1\n",
    "                elif board[j][i] == 'X':\n",
    "                    col_x_cnt += 1\n",
    "                else:\n",
    "                    black = True\n",
    "            if row_o_cnt == n or col_o_cnt == n:\n",
    "                return 'O'\n",
    "            if row_x_cnt == n or col_x_cnt == n:\n",
    "                return 'X'\n",
    "        dia1_o_cnt = 0\n",
    "        dia1_x_cnt = 0\n",
    "        dia2_o_cnt = 0\n",
    "        dia2_x_cnt = 0\n",
    "        for i in range(n):\n",
    "            if board[i][i] == 'O':\n",
    "                dia1_o_cnt += 1\n",
    "            elif board[i][i] == 'X':\n",
    "                dia1_x_cnt += 1\n",
    "            if board[n - i - 1][i] == 'O':\n",
    "                dia2_o_cnt += 1\n",
    "            elif board[n - i - 1][i] == 'X':\n",
    "                dia2_x_cnt += 1\n",
    "        if dia1_x_cnt == n or dia2_x_cnt == n:\n",
    "            return 'X'\n",
    "        if dia1_o_cnt == n or dia2_o_cnt == n:\n",
    "            return 'O'\n",
    "        return 'Pending' if black else 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            s = c * n\n",
    "            return any([\n",
    "                any(row == s for row in board),\n",
    "                any(col == s for col in map(\"\".join,zip(*board))),#遍历列\n",
    "                all(board[i][i] == c for i in range(n)),\n",
    "                all(board[j][n-1-j] == c for j in range(n))\n",
    "            ])\n",
    "        \n",
    "        if check(\"X\"):\n",
    "            return \"X\"\n",
    "        if check(\"O\"):\n",
    "            return \"O\"\n",
    "        if \" \" in \"\".join(board):\n",
    "            return \"Pending\"\n",
    "        return \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        if self.wins(board, \"X\"):\n",
    "            return \"X\"\n",
    "        if self.wins(board, \"O\"):\n",
    "            return \"O\"\n",
    "        freq_x = self.count(board, \"X\")\n",
    "        freq_o = self.count(board, \"O\")\n",
    "        if freq_x + freq_o == len(board) * len(board):\n",
    "            return \"Draw\"\n",
    "        return \"Pending\"\n",
    "\n",
    "    def count(self, board: List[str], c: str) -> int:\n",
    "        n = len(board)\n",
    "        freq = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == c:\n",
    "                    freq += 1\n",
    "        return freq\n",
    "\n",
    "    def wins(self, board: List[str], c: str) -> bool:\n",
    "        n = len(board)\n",
    "        for i in range(n):\n",
    "            is_same = True\n",
    "            for j in range(n):\n",
    "                if board[i][j] != c:\n",
    "                    is_same = False\n",
    "                    break\n",
    "            if is_same:\n",
    "                return True\n",
    "        for j in range(n):\n",
    "            is_same = True\n",
    "            for i in range(n):\n",
    "                if board[i][j] != c:\n",
    "                    is_same = False\n",
    "                    break\n",
    "            if is_same:\n",
    "                return True\n",
    "        is_same = True\n",
    "        for i in range(n):\n",
    "            if board[i][i] != c:\n",
    "                is_same = False\n",
    "                break\n",
    "        if is_same:\n",
    "            return True\n",
    "        is_same = True\n",
    "        for i in range(n):\n",
    "            if board[i][n - i - 1] != c:\n",
    "                is_same = False\n",
    "                break\n",
    "        return is_same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n=len(board)\n",
    "        def check(ch):\n",
    "            s=ch*n\n",
    "            return any((\n",
    "                any(row==s for row in board),\n",
    "                any(col==s for col in map(''.join,zip(*board))),\n",
    "                all(board[i][i]==ch for i in range(n)),\n",
    "                all(board[i][n-i-1]==ch for i in range(n))\n",
    "            ))\n",
    "        if check('X'): return 'X'\n",
    "        if check('O'): return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        if self.checkWin('X', board):\n",
    "            return 'X'\n",
    "        elif self.checkWin('O', board):\n",
    "            return 'O'\n",
    "        \n",
    "        for line in board:\n",
    "            if ' ' in line:\n",
    "                return 'Pending'\n",
    "        \n",
    "        return 'Draw'\n",
    "    \n",
    "    def checkWin(self, mark, board) -> bool:\n",
    "        n = len(board)\n",
    "        for line in board:\n",
    "            if line == mark * n:\n",
    "                return True \n",
    "        \n",
    "        for col in range(n):\n",
    "            if [board[row][col] for row in range(n)] == [mark] * n:\n",
    "                return True \n",
    "        \n",
    "        if [board[i][i] for i in range(n)] == [mark] * n:\n",
    "            return True \n",
    "        \n",
    "        if [board[i][n-1-i] for i in range(n)] == [mark] * n:\n",
    "            return True \n",
    "        \n",
    "        return False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        pending = False\n",
    "        for row in board:\n",
    "            if ' ' in row:\n",
    "                pending = True\n",
    "            else:\n",
    "                if len(set(row)) == 1:\n",
    "                    return row[0]\n",
    "\n",
    "        # 对第i列来说，就是每一行的row[i]\n",
    "        for i, _ in enumerate(board[0]):\n",
    "            col = tuple(row[i] for row in board)\n",
    "            if len(set(col)) == 1 and col[0] != ' ':\n",
    "                return col[0]\n",
    "\n",
    "        # 右对角线元素，就是第i行的第i个元素\n",
    "        r_diagonal = tuple(v[i] for i, v in enumerate(board))\n",
    "        if len(set(r_diagonal)) == 1 and r_diagonal[0] in ('X', 'O'):\n",
    "            return r_diagonal[0]\n",
    "\n",
    "        # 左对角线元素，就是第i行的第n - i个元素\n",
    "        l_diagonal = tuple(v[n - 1 - i] for i, v in enumerate(board))\n",
    "        if len(set(l_diagonal)) == 1 and l_diagonal[0] in ('X', 'O'):\n",
    "            return l_diagonal[0]\n",
    "\n",
    "        return \"Pending\" if pending else \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        board_len = len(board)\n",
    "\n",
    "        def check(cha):\n",
    "            deal_cha = cha * board_len\n",
    "\n",
    "            found = any((\n",
    "                # 行判断：只需要判断board是否包含等于deal_cha的行\n",
    "                any(row == deal_cha for row in board),\n",
    "                # 列判断：使用zip把列表中的列取出，再判断\n",
    "                any(col == deal_cha for col in map(''.join, zip(*board))),\n",
    "                # 对角线判断\n",
    "                all(board[i][i] == cha for i in range(board_len)),\n",
    "                # 反对角线判断\n",
    "                all(board[i][board_len-i-1] == cha for i in range(board_len))\n",
    "            ))\n",
    "            return found\n",
    "        if check(\"X\"): return \"X\"\n",
    "        if check(\"O\"): return \"O\"\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def single_element(lst) -> bool:\n",
    "    if len(set(lst)) == 1 and lst[0] != ' ':\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        pending = False\n",
    "        for row in board:\n",
    "            if ' ' in row:\n",
    "                pending = True\n",
    "            else:\n",
    "                if len(set(row)) == 1:\n",
    "                    return row[0]\n",
    "\n",
    "        # 对第i列来说，就是每一行的row[i]\n",
    "        for i, _ in enumerate(board[0]):\n",
    "            col = tuple(row[i] for row in board)\n",
    "            if single_element(col):\n",
    "                return col[0]\n",
    "\n",
    "        # 右对角线元素，就是第i行的第i个元素\n",
    "        r_diagonal = tuple(v[i] for i, v in enumerate(board))\n",
    "        if single_element(r_diagonal):\n",
    "            return r_diagonal[0]\n",
    "\n",
    "        # 左对角线元素，就是第i行的第n - i个元素\n",
    "        l_diagonal = tuple(v[n - 1 - i] for i, v in enumerate(board))\n",
    "        if single_element(l_diagonal):\n",
    "            return l_diagonal[0]\n",
    "\n",
    "        return \"Pending\" if pending else \"Draw\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n=len(board)\n",
    "        def check(ch):\n",
    "            s=ch*n\n",
    "            return any((\n",
    "                any(row==s for row in board),\n",
    "                any(col==s for col in map(''.join,zip(*board))),\n",
    "                all(board[i][i]==ch for i in range(n)),\n",
    "                all(board[i][n-i-1]==ch for i in range(n))\n",
    "            ))\n",
    "        if check('X'): return 'X'\n",
    "        if check('O'): return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        # 判断是否有胜利\n",
    "        n = len(board)\n",
    "        for r in range(n):\n",
    "            flag = True\n",
    "            for c in range(n):\n",
    "                if board[r][c] != board[r][0] or board[r][c] == \" \":\n",
    "                    flag = False\n",
    "            if flag:\n",
    "                return board[r][0]\n",
    "        for c in range(n):\n",
    "            flag = True\n",
    "            for r in range(n):\n",
    "                if board[r][c] != board[0][c] or board[r][c] == \" \":\n",
    "                    flag = False\n",
    "            if flag:\n",
    "                return board[0][c]\n",
    "        flag = True\n",
    "        for r in range(n):\n",
    "            if board[r][r] != board[0][0] or board[r][r] == \" \":\n",
    "                flag = False\n",
    "        if flag:\n",
    "            return board[0][0]\n",
    "        flag = True\n",
    "        for r in range(n):\n",
    "            if board[r][n - 1 - r] != board[0][n - 1] or board[r][n - 1 -r] == \" \":\n",
    "                flag = False\n",
    "        if flag:\n",
    "            return board[0][n - 1]\n",
    "        # 判断是否有空格\n",
    "        if \" \" in ''.join(board):\n",
    "            return \"Pending\"\n",
    "        else:\n",
    "            return \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n=len(board)\n",
    "        dia=[set(),set()]\n",
    "        column=[set() for _ in range(n)]\n",
    "        sign=0\n",
    "        for index_row,row in enumerate(board):\n",
    "            if len(set(row))==1 and row[0]!=' ':\n",
    "                return row[0]\n",
    "            for index in range(len(row)):\n",
    "                if row[index]==' ':\n",
    "                    sign=1\n",
    "                column[index].add(row[index])\n",
    "                if index_row==index:\n",
    "                    dia[0].add(row[index])\n",
    "                if index==(n-1)-index_row:\n",
    "                    dia[1].add(row[index])\n",
    "        \n",
    "        if len(dia[0])==1 and ' ' not in dia[0]:\n",
    "            return list(dia[0])[0]\n",
    "        if len(dia[1])==1 and ' ' not in dia[1]:\n",
    "            return list(dia[1])[0]   \n",
    "\n",
    "        for c1 in column:\n",
    "            if len(c1)==1 and ' ' not in c1:\n",
    "                return list(c1)[0]\n",
    "\n",
    "        return 'Pending' if sign!=0 else 'Draw'    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        \n",
    "        contains_space = False\n",
    "        for r in board:\n",
    "            r_ = set(r)\n",
    "            if len(r_) == 1 and list(r_)[0] in (\"O\", \"X\"):\n",
    "                return list(r_)[0]\n",
    "            else:\n",
    "                if \" \" in r:\n",
    "                    contains_space = True\n",
    "        \n",
    "        for c in zip(*board):\n",
    "            c_ = set(c)\n",
    "            if len(c_) == 1 and list(c_)[0] in (\"O\", \"X\"):\n",
    "                return list(c_)[0]\n",
    "            else:\n",
    "                if \" \" in c:\n",
    "                    contains_space = True\n",
    "        \n",
    "        n = len(board)\n",
    "        triangle = set()\n",
    "        atriangle = set()\n",
    "        for i in range(n):\n",
    "            triangle.add(board[i][i])\n",
    "            atriangle.add(board[i][n-i-1])\n",
    "\n",
    "        if len(triangle) == 1 and list(triangle)[0] in (\"O\", \"X\"):\n",
    "            return list(triangle)[0]\n",
    "        if len(atriangle) == 1 and list(atriangle)[0] in (\"O\", \"X\"):\n",
    "            return list(atriangle)[0]\n",
    "        \n",
    "        return \"Pending\" if contains_space else \"Draw\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        full = True\n",
    "        n = len(board)\n",
    "        t2 = False\n",
    "        t3 = True\n",
    "        t4 = True\n",
    "        for i in range(n):\n",
    "            tem = []\n",
    "            if \"X\"not in board[i] and ' ' not in board[i]:\n",
    "                return \"O\"\n",
    "            if \"O\"not in board[i] and ' ' not in board[i]:\n",
    "                return \"X\"\n",
    "            for j in range(n):\n",
    "                if board[j][i] == ' ':\n",
    "                    full = False\n",
    "                tem.append(board[j][i])\n",
    "            print(tem)\n",
    "            if len(set(tem)) ==1 and ' ' not in tem:  \n",
    "                return tem[0]\n",
    "            elif set(tem) !=1 or ' '  in tem:\n",
    "                tem = []\n",
    "        for i in range(n):\n",
    "            if i > 0 and board[i][i] !=board[i-1][i-1] or board[i][i] ==' ' :\n",
    "                t3 = False\n",
    "                break\n",
    "        if t3:\n",
    "            return board[i][i]\n",
    "        for i in range(n):\n",
    "            if  i < n-1 and board[i][n-i-1] !=board[i+1][n-i-2] or board[i][n-i-1] ==' ':\n",
    "                t4 = False\n",
    "                print('bore',i)\n",
    "                break\n",
    "        if t4:\n",
    "            return board[0][-1]\n",
    "        if not full:\n",
    "            return  \"Pending\"\n",
    "        return  \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        rows = [0] * n\n",
    "        cols = [0] * n\n",
    "        dg = udg = 0\n",
    "        has_empty_grid = False\n",
    "        for i, row in enumerate(board):\n",
    "            for j, c in enumerate(row):\n",
    "                v = 1 if c == 'X' else -1\n",
    "                if c == ' ':\n",
    "                    has_empty_grid = True\n",
    "                    v = 0\n",
    "                rows[i] += v\n",
    "                cols[j] += v\n",
    "                if i == j:\n",
    "                    dg += v\n",
    "                if i + j + 1 == n:\n",
    "                    udg += v\n",
    "        if any(v == n for v in rows) or any(v == n for v in cols) or dg == n or udg == n:\n",
    "            return 'X'\n",
    "        if any(v == -n for v in rows) or any(v == -n for v in cols) or dg == -n or udg == -n:\n",
    "            return 'O'\n",
    "        return 'Pending' if has_empty_grid else 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        diag,diag1 = '',''\n",
    "        column = ['']*n\n",
    "        over = True\n",
    "        for i in range(n):\n",
    "            if ' 'in board[i]:\n",
    "                over = False\n",
    "            for j in range(n):\n",
    "                if i==j:\n",
    "                    diag+=board[i][j]\n",
    "                if i+j==n-1:\n",
    "                    diag1+=board[i][j]\n",
    "                column[j]+=board[i][j]\n",
    "        board += column+[diag,diag1]\n",
    "        # print(board)\n",
    "        for c in board:\n",
    "            if len(set(c))==1 and ' ' not in c:\n",
    "                return c[0]\n",
    "        return 'Draw' if over else 'Pending'\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        length = len(board)\n",
    "        left = 0  # 左斜线\n",
    "        right = 0  # 右斜线\n",
    "        flag = False  # 记录有没有空格\n",
    "\n",
    "        for i in range(length):\n",
    "            heng = 0\n",
    "            zong = 0\n",
    "\n",
    "            for j in range(length):\n",
    "                heng += ord(board[i][j])\n",
    "                zong += ord(board[j][i])\n",
    "\n",
    "                if board[i][j] == ' ':\n",
    "                    flag = True\n",
    "\n",
    "            # 横纵检查\n",
    "            if heng == ord('X') * length or zong == ord('X') * length:\n",
    "                return 'X'\n",
    "            if heng == ord('O') * length or zong == ord('O') * length:\n",
    "                return 'O'\n",
    "\n",
    "            # 两条斜线上的相加\n",
    "            left += ord(board[i][i])\n",
    "            right += ord(board[i][length - i - 1])\n",
    "\n",
    "        # 两条斜线检查\n",
    "        if left == ord('X') * length or right == ord('X') * length:\n",
    "            return 'X'\n",
    "        if left == ord('O') * length or right == ord('O') * length:\n",
    "            return 'O'\n",
    "\n",
    "        if flag:\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "        def check(x):\n",
    "            if all(k == 'X' for k in x) or all(k == 'O' for k in x):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        for j in range(m):\n",
    "            col = [i[j] for i in board]\n",
    "            if check(col):\n",
    "                return col[0]\n",
    "        for i in board:\n",
    "            if check(i):\n",
    "                return i[0]\n",
    "        mix_a = []\n",
    "        mix_b = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == j:\n",
    "                    mix_a.append(board[i][j])\n",
    "                elif i + j == n -1:\n",
    "                    mix_b.append(board[i][j])\n",
    "        if check(mix_a):\n",
    "            return mix_a[0]\n",
    "        if check(mix_b):\n",
    "            return mix_b[0]\n",
    "        for i in board:\n",
    "            for j in i:\n",
    "                if j == ' ':\n",
    "                    return 'Pending'\n",
    "        return 'Draw'\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board[0])\n",
    "        \n",
    "        heng = [True] * n\n",
    "        shu = [True] * n\n",
    "        duijiao = [True] * 2\n",
    "        kongwei = False\n",
    "        #横着\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if heng[i] == True and board[i][0] != board[i][j]:\n",
    "                    heng[i] = False\n",
    "        for k in range(len(heng)):\n",
    "            if heng[k] == True and board[k][0] != \" \":\n",
    "                return board[k][0]\n",
    "\n",
    "        #竖的和对角\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if kongwei == False and board[i][j] == \" \":\n",
    "                    kongwei = True\n",
    "                if shu[j] == True and board[0][j] != board[i][j]:\n",
    "                    shu[j] = False\n",
    "                if duijiao[0] == True and i == j and board[0][0] != board[i][j]:\n",
    "                    duijiao[0] = False\n",
    "                if duijiao[1] == True and j == n-1-i and board[0][n-1] != board[i][j]:\n",
    "                    duijiao[1] = False\n",
    "        if duijiao[0] == True and board[0][0] != \" \":\n",
    "            return board[0][0]\n",
    "        if duijiao[1] == True and board[0][n-1] != \" \":\n",
    "            return board[0][n-1]\n",
    "        for m in range(len(shu)):\n",
    "            if shu[m] == True and board[0][m] != \" \":\n",
    "                return board[0][m]\n",
    "        if kongwei == True:\n",
    "            return \"Pending\"\n",
    "        else:\n",
    "            return \"Draw\"\n",
    "            \n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            s = c * n\n",
    "            return any((any(row == s for row in board),\n",
    "            any(col == s for col in map(''.join,zip(*board))),\n",
    "            all(board[i][i] == c for i in range(n)),\n",
    "            all(board[i][n-i-1] == c for i in range(n))))\n",
    "        \n",
    "        if check('X'):\n",
    "            return 'X'\n",
    "        if check('O'):\n",
    "            return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            s = c * n\n",
    "            return any((\n",
    "                any(row == s for row in board),\n",
    "                any(col == s for col in map(\"\".join,zip(*board))),\n",
    "                all(board[i][i] == c for i in range(n)),\n",
    "                all(board[i][n - i - 1] == c for i in range(n))\n",
    "            ))\n",
    "        if check(\"O\"):\n",
    "            return \"O\"\n",
    "        if check(\"X\"):\n",
    "            return \"X\"\n",
    "        if \" \" in \"\".join(board):\n",
    "            return \"Pending\"\n",
    "        return \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board[0])\n",
    "        #先考虑第一行\n",
    "        heng = [True] * n\n",
    "        shu = [True] * n\n",
    "        duijiao = [True] * 2\n",
    "        kongwei = False\n",
    "        #横着\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if heng[i] == True and board[i][0] != board[i][j]:\n",
    "                    heng[i] = False\n",
    "        for k in range(len(heng)):\n",
    "            if heng[k] == True and board[k][0] != \" \":\n",
    "                return board[k][0]\n",
    "\n",
    "        #竖的和对角\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if kongwei == False and board[i][j] == \" \":\n",
    "                    kongwei = True\n",
    "                if shu[j] == True and board[0][j] != board[i][j]:\n",
    "                    shu[j] = False\n",
    "                if duijiao[0] == True and i == j and board[0][0] != board[i][j]:\n",
    "                    duijiao[0] = False\n",
    "                if duijiao[1] == True and j == n-1-i and board[0][n-1] != board[i][j]:\n",
    "                    duijiao[1] = False\n",
    "        if duijiao[0] == True and board[0][0] != \" \":\n",
    "            return board[0][0]\n",
    "        if duijiao[1] == True and board[0][n-1] != \" \":\n",
    "            return board[0][n-1]\n",
    "        for m in range(len(shu)):\n",
    "            if shu[m] == True and board[0][m] != \" \":\n",
    "                return board[0][m]\n",
    "        if kongwei == True:\n",
    "            return \"Pending\"\n",
    "        else:\n",
    "            return \"Draw\"\n",
    "            \n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        havespace=False\n",
    "        tmp = []\n",
    "        for item in board:\n",
    "            if ' ' in item:\n",
    "                havespace=True\n",
    "        for i in range(len(board)):\n",
    "            if ' ' in board[i]:\n",
    "                continue\n",
    "            elif 'O' in board[i] and 'X' not in board[i]:\n",
    "                return 'O'\n",
    "            elif 'O' not in board[i] and 'X' in board[i]:\n",
    "                return 'X'\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board)):\n",
    "                if board[j][i]==' ':\n",
    "                    tmp=[]\n",
    "                    break\n",
    "                elif board[j][i]=='O':\n",
    "                    if 'X' in tmp:\n",
    "                        tmp=[]\n",
    "                        break\n",
    "                    else:\n",
    "                        tmp.append('O')\n",
    "                elif board[j][i]=='X':\n",
    "                    if 'O' in tmp:\n",
    "                        tmp=[]\n",
    "                        break\n",
    "                    else:\n",
    "                        tmp.append('X')\n",
    "            if len(tmp)==len(board):\n",
    "                return tmp[0]   \n",
    "        for i in range(len(board)):\n",
    "            if board[i][i]==' ':\n",
    "                tmp=[]\n",
    "                break\n",
    "            elif board[i][i]=='O':\n",
    "                if 'X' in tmp:\n",
    "                    tmp=[]\n",
    "                    break\n",
    "                else:\n",
    "                    tmp.append('O')\n",
    "            elif board[i][i]=='X':\n",
    "                if 'O' in tmp:\n",
    "                    tmp=[]\n",
    "                    break\n",
    "                else:\n",
    "                    tmp.append('X')\n",
    "            if len(tmp)==len(board):\n",
    "                return tmp[0]\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            if board[i][len(board)-1-i]==' ':\n",
    "                tmp=[]\n",
    "                break\n",
    "            elif board[i][len(board)-1-i]=='O':\n",
    "                if 'X' in tmp:\n",
    "                    tmp=[]\n",
    "                    break\n",
    "                else:\n",
    "                    tmp.append('O')\n",
    "            elif board[i][len(board)-1-i]=='X':\n",
    "                if 'O' in tmp:\n",
    "                    tmp=[]\n",
    "                    break\n",
    "                else:\n",
    "                    tmp.append('X')\n",
    "            if len(tmp)==len(board):\n",
    "                return tmp[0]\n",
    "        if havespace:\n",
    "            return \"Pending\"\n",
    "        else: return \"Draw\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        for row in board:\n",
    "            element = set(list(row))\n",
    "            if len(element) == 1:\n",
    "                element = element.pop()\n",
    "                if element != ' ':\n",
    "                    return element\n",
    "\n",
    "        for index, value in enumerate(board[0]):            \n",
    "            column = (row[index] for row in board)\n",
    "            element = set(column)\n",
    "            if len(element) == 1:\n",
    "                element = element.pop()\n",
    "                if element != ' ':\n",
    "                    return element\n",
    "\n",
    "        nw = (value[index] for index, value in enumerate(board))\n",
    "        element = set(nw)\n",
    "\n",
    "        if len(element) == 1:\n",
    "                element = element.pop()\n",
    "                if element != ' ':\n",
    "                    return element\n",
    "        board_len = len(board)\n",
    "        ne = (value[board_len - index - 1] for index, value in enumerate(board))\n",
    "        element = set(ne)\n",
    "\n",
    "        if len(element) == 1:\n",
    "                element = element.pop()\n",
    "                if element != ' ':\n",
    "                    return element\n",
    "        for row in board:\n",
    "            if ' ' in row:\n",
    "                return 'Pending'\n",
    "        return 'Draw'\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            s = c * n\n",
    "            return any((\n",
    "                any(row == s for row in board),\n",
    "                any(col == s for col in map(''.join, zip(*board))),\n",
    "                all(board[i][i] == c for i in range(n)),\n",
    "                all(board[i][n - i - 1] == c for i in range(n))\n",
    "            ))\n",
    "        if check('X'):\n",
    "            return 'X'\n",
    "        if check('O'):\n",
    "            return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "        for j in range(m):\n",
    "            col = [i[j] for i in board]\n",
    "            if all(k == 'X' for k in col):\n",
    "                return 'X'\n",
    "            if all(k == 'O' for k in col):\n",
    "                return 'O'\n",
    "        for i in board:\n",
    "            if all(k == 'X' for k in i):\n",
    "                return 'X'\n",
    "            if all(k == 'O' for k in i):\n",
    "                return 'O'\n",
    "        mix_a = []\n",
    "        mix_b = []\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if i == j:\n",
    "                    mix_a.append(board[i][j])\n",
    "                elif i + j == n -1:\n",
    "                    mix_b.append(board[i][j])\n",
    "        if all(i == 'X' for i in mix_a):\n",
    "            return 'X'\n",
    "        if all(i == 'O' for i in mix_a):\n",
    "            return 'O'\n",
    "        if all(i == 'X' for i in mix_b):\n",
    "            return 'X'\n",
    "        if all(i == 'O' for i in mix_b):\n",
    "            return 'O'\n",
    "        for i in board:\n",
    "            for j in i:\n",
    "                if j == ' ':\n",
    "                    return 'Pending'\n",
    "        return 'Draw'\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        length = len(board)\n",
    "        left = 0  # 左斜线\n",
    "        right = 0  # 右斜线\n",
    "        flag = False  # 记录有没有空格\n",
    "\n",
    "        for i in range(length):\n",
    "            heng = 0\n",
    "            zong = 0\n",
    "\n",
    "            for j in range(length):\n",
    "                heng += ord(board[i][j])\n",
    "                zong += ord(board[j][i])\n",
    "\n",
    "                if board[i][j] == ' ':\n",
    "                    flag = True\n",
    "\n",
    "            # 横纵检查\n",
    "            if heng == ord('X') * length or zong == ord('X') * length:\n",
    "                return 'X'\n",
    "            if heng == ord('O') * length or zong == ord('O') * length:\n",
    "                return 'O'\n",
    "\n",
    "            # 两条斜线上的相加\n",
    "            left += ord(board[i][i])\n",
    "            right += ord(board[i][length - i - 1])\n",
    "\n",
    "        # 两条斜线检查\n",
    "        if left == ord('X') * length or right == ord('X') * length:\n",
    "            return 'X'\n",
    "        if left == ord('O') * length or right == ord('O') * length:\n",
    "            return 'O'\n",
    "\n",
    "        if flag:\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        for i in range(n):\n",
    "            if board[i] == 'X'*n or board[i] == 'O'*n:\n",
    "                return board[i][0]\n",
    "        for col in map(''.join, zip(*board)):\n",
    "            if col == 'X'*n or col == 'O'*n:\n",
    "                return col[0]\n",
    "        if all(board[i][i] == 'X' for i in range(n)):\n",
    "            return 'X'\n",
    "        if all(board[i][i] == 'O' for i in range(n)):\n",
    "            return 'O'\n",
    "        if all(board[i][n-1-i] == 'X' for i in range(n)):\n",
    "            return 'X'\n",
    "        if all(board[i][n-1-i] == 'O' for i in range(n)):\n",
    "            return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        boards = {'col': {\n",
    "            i: board[0][i] for i in range(n)\n",
    "        }, 'row': {\n",
    "            i: board[i][0] for i in range(n)\n",
    "        }, '0': board[0][0], 'n': board[0][n-1]\n",
    "        }\n",
    "        pending = 'Draw'\n",
    "        for i in range(n):\n",
    "            if boards.get('0') and (board[i][i] != boards.get('0') or board[i][i] == ' '):\n",
    "                boards.pop('0')\n",
    "            if boards.get('n') and (board[i][n-1-i] != boards.get('n') or board[i][n-1-i] == ' '):\n",
    "                boards.pop('n')\n",
    "            for j in range(n):\n",
    "                if board[i][j] == ' ':\n",
    "                    pending = 'Pending'\n",
    "                    if boards.get('row').get(i):\n",
    "                        boards.get('row').pop(i)\n",
    "                    if boards.get('col').get(j):\n",
    "                        boards.get('col').pop(j)\n",
    "                if boards.get('row').get(i) and board[i][j] != boards.get('row').get(i):\n",
    "                    boards.get('row').pop(i)\n",
    "                if boards.get('col').get(j) and board[i][j] != boards.get('col').get(j):\n",
    "                    boards.get('col').pop(j)\n",
    "\n",
    "\n",
    "        if boards.get('row'):\n",
    "            for k, v in boards.get('row').items():\n",
    "                return v\n",
    "        if boards.get('col'):\n",
    "            for k, v in boards.get('col').items():\n",
    "                return v\n",
    "        if boards.get('0'):\n",
    "            return boards.get('0')\n",
    "        if boards.get('n'):\n",
    "            return boards.get('n')\n",
    "        return pending"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board[0])\n",
    "        heng = [True] * n\n",
    "        shu = [True] * n\n",
    "        duijiao = [True] * 2\n",
    "        kongwei = False\n",
    "    \n",
    "       \n",
    "\n",
    "        #竖的和对角\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if heng[i] == True and board[i][0] != board[i][j]:\n",
    "                    heng[i] = False\n",
    "                if kongwei == False and board[i][j] == \" \":\n",
    "                    kongwei = True\n",
    "                if shu[j] == True and board[0][j] != board[i][j]:\n",
    "                    shu[j] = False\n",
    "                if duijiao[0] == True and i == j and board[0][0] != board[i][j]:\n",
    "                    duijiao[0] = False\n",
    "                if duijiao[1] == True and j == n-1-i and board[0][n-1] != board[i][j]:\n",
    "                    duijiao[1] = False\n",
    "        if duijiao[0] == True and board[0][0] != \" \":\n",
    "            return board[0][0]\n",
    "        if duijiao[1] == True and board[0][n-1] != \" \":\n",
    "            return board[0][n-1]\n",
    "        for k in range(len(heng)):\n",
    "            if heng[k] == True and board[k][0] != \" \":\n",
    "                return board[k][0]\n",
    "            if shu[k] == True and board[0][k] != \" \":\n",
    "                return board[0][k]\n",
    "        if kongwei == True:\n",
    "            return \"Pending\"\n",
    "        else:\n",
    "            return \"Draw\"\n",
    "            \n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        diag,diag1 = '',''\n",
    "        column = ['']*n\n",
    "        over = True\n",
    "        for i in range(n):\n",
    "            if ' 'in board[i]:\n",
    "                over = False\n",
    "            for j in range(n):\n",
    "                if i==j:\n",
    "                    diag+=board[i][j]\n",
    "                if i+j==n-1:\n",
    "                    diag1+=board[i][j]\n",
    "                column[j]+=board[i][j]\n",
    "        board += column+[diag,diag1]\n",
    "        # print(board)\n",
    "        for c in board:\n",
    "            if len(set(c))==1 and ' ' not in c:\n",
    "                return c[0]\n",
    "        return 'Draw' if over else 'Pending'\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        diag,diag1 = '',''\n",
    "        column = ['']*n\n",
    "        over = True\n",
    "        for i in range(n):\n",
    "            if ' 'in board[i]:\n",
    "                over = False\n",
    "            for j in range(n):\n",
    "                if i==j:\n",
    "                    diag+=board[i][j]\n",
    "                if i+j==n-1:\n",
    "                    diag1+=board[i][j]\n",
    "                column[j]+=board[i][j]\n",
    "        board += column+[diag,diag1]\n",
    "        # print(board)\n",
    "        for c in board:\n",
    "            if len(set(c))==1 and ' ' not in c:\n",
    "                return c[0]\n",
    "        return 'Draw' if over else 'Pending'\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        \n",
    "        for x in range(n):\n",
    "            if board[x][0] != ' ' and all(board[x][0] == board[x][i] for i in range(n)):\n",
    "                return board[x][0]\n",
    "            if board[0][x] != ' ' and all(board[0][x] == board[i][x] for i in range(n)):\n",
    "                return board[0][x]\n",
    "        \n",
    "        if board[0][0] != ' ' and all(board[0][0] == board[i][i] for i in range(n)):\n",
    "            return board[0][0]\n",
    "        \n",
    "        if board[0][n - 1] != ' ' and all(board[0][n - 1] == board[i][n - i - 1] for i in range(n)):\n",
    "            return board[0][n - 1]\n",
    "        \n",
    "        if ' ' in ''.join(board):\n",
    "            return \"Pending\"\n",
    "        \n",
    "        return \"Draw\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        XX = 'X' * n\n",
    "        OO = 'O' * n\n",
    "        \n",
    "        if XX in board:\n",
    "            return 'X'\n",
    "        elif OO in board:\n",
    "            return 'O'\n",
    "        \n",
    "        l = [\"\".join(board[i][j] for i in range(n))  for j in range(n)]\n",
    "        if XX in l:\n",
    "            return 'X'\n",
    "        elif OO in l:\n",
    "            return 'O'\n",
    "        \n",
    "        X = [\"\".join(board[i][i] for i in range(n)), \"\".join(board[i][-i - 1] for i in range(n))]\n",
    "\n",
    "        if XX in X:\n",
    "            return 'X'\n",
    "        elif OO in X:\n",
    "            return 'O'\n",
    "        \n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        else:\n",
    "            return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board[0])\n",
    "        heng = [True] * n\n",
    "        shu = [True] * n\n",
    "        duijiao = [True] * 2\n",
    "        kongwei = False\n",
    "        #横着\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if heng[i] == True and board[i][0] != board[i][j]:\n",
    "                    heng[i] = False\n",
    "        for k in range(len(heng)):\n",
    "            if heng[k] == True and board[k][0] != \" \":\n",
    "                return board[k][0]\n",
    "\n",
    "        #竖的和对角\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if kongwei == False and board[i][j] == \" \":\n",
    "                    kongwei = True\n",
    "                if shu[j] == True and board[0][j] != board[i][j]:\n",
    "                    shu[j] = False\n",
    "                if duijiao[0] == True and i == j and board[0][0] != board[i][j]:\n",
    "                    duijiao[0] = False\n",
    "                if duijiao[1] == True and j == n-1-i and board[0][n-1] != board[i][j]:\n",
    "                    duijiao[1] = False\n",
    "        if duijiao[0] == True and board[0][0] != \" \":\n",
    "            return board[0][0]\n",
    "        if duijiao[1] == True and board[0][n-1] != \" \":\n",
    "            return board[0][n-1]\n",
    "        for m in range(len(shu)):\n",
    "            if shu[m] == True and board[0][m] != \" \":\n",
    "                return board[0][m]\n",
    "        if kongwei == True:\n",
    "            return \"Pending\"\n",
    "        else:\n",
    "            return \"Draw\"\n",
    "            \n",
    "            \n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        # 检查行\n",
    "        for i in range(len(board)):\n",
    "            if len(set(board[i])) == 1 and board[i][0]!=' ':\n",
    "                return board[i][0]\n",
    "        # 检查列\n",
    "        row = 0\n",
    "        col = 0\n",
    "        n = len(board)\n",
    "        while col!=n:\n",
    "            temp = board[row][col]\n",
    "            while True:\n",
    "                row+=1\n",
    "                if row==n:\n",
    "                    return temp\n",
    "                if board[row][col]!=temp or board[row][col]==' ':\n",
    "                    row=0\n",
    "                    break\n",
    "            col+=1\n",
    "        # 正对角线\n",
    "        row = col =0\n",
    "        temp = board[0][0]\n",
    "        while True:\n",
    "            row+=1\n",
    "            col+=1\n",
    "            if row==n:\n",
    "                return temp\n",
    "            if temp!=board[row][col] or board[row][col] == ' ':\n",
    "                break\n",
    "        # 负对角线\n",
    "        row = 0\n",
    "        col = n-1\n",
    "        temp = board[row][col]\n",
    "        while True:\n",
    "            row+=1\n",
    "            col-=1\n",
    "            if row==n:\n",
    "                return temp\n",
    "            if temp!=board[row][col] or board[row][col] == ' ':\n",
    "                break\n",
    "        # 程序到这里说明没判断出来输赢 看一下是否有空值，有则未结束 否则平局\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == ' ':\n",
    "                    return \"Pending\"\n",
    "        return\"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            s = c * n\n",
    "            return any(\n",
    "                (\n",
    "                    any(row == s for row in board),\n",
    "                    any(col == s for col in map(\"\".join, zip(*board))),\n",
    "                    all(board[i][i] == c for i in range(n)),\n",
    "                    all(board[i][n - i - 1] == c for i in range(n)),\n",
    "                )\n",
    "            )\n",
    "\n",
    "        if check(\"X\"):\n",
    "            return \"X\"\n",
    "        if check(\"O\"):\n",
    "            return \"O\"\n",
    "        if \" \" in \"\".join(board):\n",
    "            return \"Pending\"\n",
    "        return \"Draw\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "\n",
    "        n = len(board)\n",
    "        \n",
    "        def check(ch):\n",
    "            s = ch * n\n",
    "            return any((\n",
    "                any(row == s for row in board),\n",
    "                any(col == s for col in map(''.join, zip(*board))),\n",
    "                all(board[i][i] == ch for i in range(n)),\n",
    "                all(board[i][n - i - 1] == ch for i in range(n)),\n",
    "            ))\n",
    "        \n",
    "        if check('X'): return 'X'\n",
    "        if check('O'): return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            return any((\n",
    "                any([all([i==c for i in row]) for row in board]), # any row all c\n",
    "                any([all([i==c for i in col]) for col in zip(*board)]), # any column all c\n",
    "                all([board[i][i]==c for i in range(n)]), # positive diagonal\n",
    "                all([board[i][n-i-1]==c for i in range(n)])\n",
    "            ))\n",
    "        if check(\"X\"):\n",
    "            return \"X\"\n",
    "        if check(\"O\"):\n",
    "            return \"O\"\n",
    "\n",
    "        if any([\" \" in row for row in board]):\n",
    "            return \"Pending\"\n",
    "        return \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        def check(c):\n",
    "            s = c * n\n",
    "            return any((\n",
    "                any(row == s for row in board),\n",
    "                any(col == s for col in map(''.join, zip(*board))),\n",
    "                all(board[i][i] == c for i in range(n)),\n",
    "                all(board[i][n - i - 1] == c for i in range(n))\n",
    "            ))\n",
    "        if check('X'):\n",
    "            return 'X'\n",
    "        if check('O'):\n",
    "            return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        x_board = [[0] * n for _ in range(n)]\n",
    "        o_board = [[0] * n for _ in range(n)]\n",
    "        has_empty = False\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \" \":\n",
    "                    has_empty = True\n",
    "                elif board[i][j] == \"O\":\n",
    "                    o_board[i][j] = 1\n",
    "                else:\n",
    "                    x_board[i][j] = 1\n",
    "        \n",
    "        if self.winCheck(x_board):\n",
    "            return \"X\"\n",
    "        \n",
    "        if self.winCheck(o_board):\n",
    "            return \"O\"\n",
    "        \n",
    "        if has_empty:\n",
    "            return \"Pending\"\n",
    "        \n",
    "        return \"Draw\"\n",
    "    \n",
    "    def winCheck(self, board):\n",
    "        n = len(board)\n",
    "        for i in range(n):\n",
    "            win = True\n",
    "            for j in range(n):\n",
    "                if not board[i][j]:\n",
    "                    win = False\n",
    "                    break\n",
    "            if win:\n",
    "                return True\n",
    "        for j in range(n):\n",
    "            win = True\n",
    "            for i in range(n):\n",
    "                if not board[i][j]:\n",
    "                    win = False\n",
    "                    break\n",
    "            if win:\n",
    "                return True\n",
    "        win = True\n",
    "        for i in range(n):\n",
    "            if not board[i][i]:\n",
    "                win = False\n",
    "                break\n",
    "        if win:\n",
    "            return True\n",
    "        win = True\n",
    "        for i in range(n):\n",
    "            if not board[i][n - i - 1]:\n",
    "                win = False\n",
    "                break\n",
    "        if win:\n",
    "            return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n=len(board)\n",
    "        def check(c):\n",
    "            s=c*n\n",
    "            return any((any(row==s for row in board), any(col==s for col in map(''.join,zip(*board))), all(board[i][i]==c for i in range(n)), all(board[i][n-1-i]==c for i in range(n))))\n",
    "        if check('X'):\n",
    "            return 'X'\n",
    "        if check('O'):\n",
    "            return 'O'\n",
    "        if ' ' in ''.join(board):\n",
    "            return 'Pending'\n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board)\n",
    "        pending = False\n",
    "        # 检查对角线\n",
    "        cnt_X = 0\n",
    "        cnt_O = 0\n",
    "        for i in range(n):\n",
    "            if board[i][i] == \" \":\n",
    "                pending = True\n",
    "                break\n",
    "            if board[i][i] == \"O\":\n",
    "                cnt_O += 1\n",
    "            else:\n",
    "                cnt_X += 1\n",
    "        if cnt_X == n: return \"X\"\n",
    "        if cnt_O == n: return \"O\"\n",
    "\n",
    "        # 检查副对角线\n",
    "        cnt_X = 0\n",
    "        cnt_O = 0\n",
    "        for i in range(n):\n",
    "            if board[i][n-1-i] == \" \":\n",
    "                pending = True\n",
    "                break\n",
    "            if board[i][n-1-i] == \"O\":\n",
    "                cnt_O += 1\n",
    "            else:\n",
    "                cnt_X += 1\n",
    "        if cnt_X == n: return \"X\"\n",
    "        if cnt_O == n: return \"O\"\n",
    "\n",
    "        # 检查每行\n",
    "        for i in range(n):\n",
    "            cnt_X = 0\n",
    "            cnt_O = 0\n",
    "            for j in range(n):\n",
    "                if board[i][j] == \" \":\n",
    "                    pending = True\n",
    "                    break\n",
    "                if board[i][j] == \"X\":\n",
    "                    cnt_X += 1\n",
    "                else:\n",
    "                    cnt_O += 1\n",
    "            if cnt_X == n: return \"X\"\n",
    "            if cnt_O == n: return \"O\"\n",
    "\n",
    "        # 检查每列\n",
    "        for j in range(n):\n",
    "            cnt_X = 0\n",
    "            cnt_O = 0\n",
    "            for i in range(n):\n",
    "                if board[i][j] == \" \":\n",
    "                    pending = True\n",
    "                    break\n",
    "                if board[i][j] == \"X\":\n",
    "                    cnt_X += 1\n",
    "                else:\n",
    "                    cnt_O += 1\n",
    "            if cnt_X == n: return \"X\"\n",
    "            if cnt_O == n: return \"O\"\n",
    "        \n",
    "        if pending: return \"Pending\"\n",
    "        return \"Draw\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        \n",
    "        contains_space = False\n",
    "        for r in board:\n",
    "            r_ = set(r)\n",
    "            if r_ == set(\"X\"):\n",
    "                return \"X\"\n",
    "            elif r_ == set(\"O\"):\n",
    "                return  \"O\"\n",
    "            else:\n",
    "                if \" \" in r:\n",
    "                    contains_space = True\n",
    "        \n",
    "        for c in zip(*board):\n",
    "            c_ = set(c)\n",
    "            if c_ == set(\"X\"):\n",
    "                return  \"X\"\n",
    "            elif c_ == set(\"O\"):\n",
    "                return \"O\"\n",
    "            else:\n",
    "                if \" \" in c:\n",
    "                    contains_space = True\n",
    "        \n",
    "        n = len(board)\n",
    "        triangle = set()\n",
    "        atriangle = set()\n",
    "        for i in range(n):\n",
    "            triangle.add(board[i][i])\n",
    "            atriangle.add(board[i][n-i-1])\n",
    "        if len(triangle) == 1 and list(triangle)[0] in (\"O\", \"X\"):\n",
    "            return list(triangle)[0]\n",
    "        if len(atriangle) == 1 and list(triangle)[0] in (\"O\", \"X\"):\n",
    "            return list(atriangle)[0]\n",
    "        \n",
    "        return \"Pending\" if contains_space else \"Draw\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n = len(board[0])\n",
    "        heng = [True] * n\n",
    "        shu = [True] * n\n",
    "        duijiao = [True] * 2\n",
    "        kongwei = False\n",
    "        #横着\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if heng[i] == True and board[i][0] != board[i][j]:\n",
    "                    heng[i] = False\n",
    "        for k in range(len(heng)):\n",
    "            if heng[k] == True and board[k][0] != \" \":\n",
    "                return board[k][0]\n",
    "\n",
    "        #竖的和对角\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if kongwei == False and board[i][j] == \" \":\n",
    "                    kongwei = True\n",
    "                if shu[j] == True and board[0][j] != board[i][j]:\n",
    "                    shu[j] = False\n",
    "                if duijiao[0] == True and i == j and board[0][0] != board[i][j]:\n",
    "                    duijiao[0] = False\n",
    "                if duijiao[1] == True and j == n-1-i and board[0][n-1] != board[i][j]:\n",
    "                    duijiao[1] = False\n",
    "        if duijiao[0] == True and board[0][0] != \" \":\n",
    "            return board[0][0]\n",
    "        if duijiao[1] == True and board[0][n-1] != \" \":\n",
    "            return board[0][n-1]\n",
    "        for m in range(len(shu)):\n",
    "            if shu[m] == True and board[0][m] != \" \":\n",
    "                return board[0][m]\n",
    "        if kongwei == True:\n",
    "            return \"Pending\"\n",
    "        else:\n",
    "            return \"Draw\"\n",
    "            \n",
    "    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        full = True\n",
    "        n = len(board)\n",
    "        t2 = False\n",
    "        t3 = True\n",
    "        t4 = True\n",
    "        for i in range(n):\n",
    "            tem = []\n",
    "\n",
    "            if \"X\"not in board[i] and ' ' not in board[i]:\n",
    "                print('t1')\n",
    "                return \"O\"\n",
    "            if \"O\"not in board[i] and ' ' not in board[i]:\n",
    "                print('t1')\n",
    "                return \"X\"\n",
    "            for j in range(n):\n",
    "                if board[j][i] == ' ':\n",
    "                    full = False\n",
    "                tem.append(board[j][i])\n",
    "            print(tem)\n",
    "            if len(set(tem)) ==1 and ' ' not in tem:\n",
    "                print('t2')    \n",
    "                return tem[0]\n",
    "            elif set(tem) !=1 or ' '  in tem:\n",
    "                tem = []\n",
    "        for i in range(n):\n",
    "            if i > 0 and board[i][i] !=board[i-1][i-1] or board[i][i] ==' ' :\n",
    "                t3 = False\n",
    "                break\n",
    "        if t3:\n",
    "            print('t3')\n",
    "            return board[i][i]\n",
    "        for i in range(n):\n",
    "            if  i < n-1 and board[i][n-i-1] !=board[i+1][n-i-2] or board[i][n-i-1] ==' ':\n",
    "                t4 = False\n",
    "                print('bore',i)\n",
    "                break\n",
    "        if t4:\n",
    "            print('t4')\n",
    "            return board[0][-1]\n",
    "        if not full:\n",
    "            return  \"Pending\"\n",
    "        return  \"Draw\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        n=len(board)\n",
    "        for i in range(n):\n",
    "            if all(board[i][j]==\"O\" for j in range(n)):\n",
    "                return 'O'\n",
    "            if all(board[i][j]==\"X\" for j in range(n)):\n",
    "                return 'X'\n",
    "        for j in range(n):\n",
    "            if all(board[i][j]==\"O\" for i in range(n)):\n",
    "                return 'O'\n",
    "            if all(board[i][j]==\"X\" for i in range(n)):\n",
    "                return 'X'\n",
    "        if all(board[i][i]==\"O\" for i in range(n)):\n",
    "            return 'O'\n",
    "        if all(board[i][i]==\"X\" for i in range(n)):\n",
    "            return 'X'\n",
    "        if all(board[i][n-1-i]==\"O\" for i in range(n)):\n",
    "            return 'O'\n",
    "        if all(board[i][n-1-i]==\"X\" for i in range(n)):\n",
    "            return 'X'\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if board[i][j]==\" \":\n",
    "                    return \"Pending\"\n",
    "        return \"Draw\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check_row(self, c):\n",
    "        # row\n",
    "        for i in range(len(self.board)):\n",
    "            ans = True\n",
    "            for j in range(len(self.board[0])):\n",
    "                if self.board[i][j] != c:\n",
    "                    ans = False\n",
    "                    break\n",
    "            if ans: return c\n",
    "    \n",
    "    def check_col(self, c):\n",
    "        # col\n",
    "        for i in range(len(self.board)):\n",
    "            ans = True\n",
    "            for j in range(len(self.board[0])):\n",
    "                if self.board[j][i] != c:\n",
    "                    ans = False\n",
    "                    break\n",
    "            if ans: return c\n",
    "\n",
    "    def check_diag(self, c):\n",
    "        # col\n",
    "        ans = True\n",
    "        for i in range(len(self.board)):\n",
    "            if self.board[i][i] != c:\n",
    "                ans = False\n",
    "                break\n",
    "        if ans: return c\n",
    "\n",
    "    def check_back_diag(self, c):\n",
    "        # col\n",
    "        ans = True\n",
    "        for i in range(len(self.board)):\n",
    "            if self.board[len(self.board)-1-i][i] != c:\n",
    "                ans = False\n",
    "                break\n",
    "        if ans: return c\n",
    "\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        self.board = board\n",
    "        for c in ['X', 'O']:\n",
    "            if self.check_row(c): return c\n",
    "            elif self.check_col(c): return c\n",
    "            elif self.check_diag(c): return c\n",
    "            elif self.check_back_diag(c): return c\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == ' ': return 'Pending'\n",
    "        \n",
    "        return 'Draw'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tictactoe(self, board: List[str]) -> str:\n",
    "        row = len(board)\n",
    "\n",
    "        result = 'Draw'\n",
    "        for val in board:\n",
    "            if val.count('X') == row:\n",
    "                return 'X'\n",
    "            elif val.count('O') == row:\n",
    "                return 'O'\n",
    "            elif val.count(' '):\n",
    "                result = 'Pending'\n",
    "\n",
    "        board_rev = list(zip(*board))\n",
    "        for val in board_rev:\n",
    "            if val.count('X') == row:\n",
    "                return 'X'\n",
    "            elif val.count('O') == row:\n",
    "                return 'O'\n",
    "            elif val.count(' '):\n",
    "                result = 'Pending'\n",
    "\n",
    "        board_angles = ['', '']\n",
    "        for i in range(row):\n",
    "            board_angles[0] += board[i][i]\n",
    "            board_angles[1] += board[row - i - 1][i]\n",
    "            \n",
    "        for val in board_angles:\n",
    "            if val.count('X') == row:\n",
    "                return 'X'\n",
    "            elif val.count('O') == row:\n",
    "                return 'O'\n",
    "            elif val.count(' '):\n",
    "                result = 'Pending'\n",
    "        return result"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
